<?php
App::uses('AppController', 'Controller');
App::uses('ComponentCollection', 'Controller');
App::uses('Hungdv7GuessGameComponent', 'Controller/Component');
App::uses('Hungdv7SudokuComponent', 'Controller/Component');

class Hungdv7TestsController extends AppController{
	public $components = array('Hungdv7GuessGame', 'Hungdv7Sudoku');
	public $autoRender = false;
	public $count;
	public $arr = array();
	
	public function guess($price, $guess1, $guess2, $guess3, $guess4){		
	 	$result = $this->GuessGame->play($price,$guess1,$guess2,$guess3,$guess4);			
		
		print_r($result);
		exit; 
	}
	
	public function runSudokuCheck(){
		$Collection = new ComponentCollection();
		$SudokuComponent = new Hungdv7SudokuComponent($Collection);
		$initialArray = array(
			array(4,3,5,2,6,9,7,8,1),
			array(6,8,2,5,7,1,4,9,3),
			array(1,9,7,8,3,4,5,6,2),
			array(8,2,6,1,9,5,3,4,7),
			array(3,7,4,6,8,2,9,1,5),
			array(9,5,1,7,4,3,6,2,8),
			array(5,1,9,3,2,6,8,7,4),
			array(2,4,8,9,5,7,1,3,6),
			array(7,6,3,4,1,8,2,5,9)				
		);

		/* print_r(json_encode($initialArray));
		exit; */
		
		$start = microtime(true);
		//$result = $this->Hungdv7Sudoku->checkSudoku2($initialArray);
		$result =  $SudokuComponent->checkSudoku2($initialArray);
		
		print_r($result);
		echo ' --- Runtime: ' . (microtime(true) - $start);
		
		exit;
	}
	
	public function sort(){
		$this->count = 0;
		
		//ramdom array
		$this->arr = array(320,5,485,7,33,6,9,40,12,46,87,102,1,8,54,37,90);
		//$this->arr = array(6,5,3,1,8,7,2,4);
		
		//reverse array
		//$arr = array(485, 320, 102, 90, 87, 54, 46, 40, 37, 33, 12, 9, 8, 7, 6, 5, 1);
			
		//nearly sorted
		//$arr = array(5,1, 7,6, 9, 8, 33, 12, 40, 37, 46, 54, 90, 87, 320,102, 485);	
		
		
		
		echo 'before sort <pre>';
		print_r($this->arr);
		echo '</pre>';
		
		$result = $this->mergeSort($this->arr);
		
		echo 'after sort <pre>';
		print_r($result);
		echo '</pre>';
		
		echo '<pre>loop=' . $this->count . '</pre>';
		
		exit;		
	}
	
	private function bubbleSort($sortArray){
		$buble = null;
		for($i=0; $i < count($sortArray); $i++){
			$swaped = 'false';
			for($j= (count($sortArray) - 1); $j>$i; $j--){
				$this->count++;
				
				//main sort
				if($sortArray[$j] < $sortArray[$j-1]){
					//swapping					
					list($sortArray[$j-1],$sortArray[$j]) = array($sortArray[$j],$sortArray[$j-1]);
					$swaped = 'true';
				}
				
				//$buble = $sortArray[$j-1];
				//$sink = $sortArray[$j];
				//echo '/ loop='. $this->count .' flg=' . $swaped . ' bubble=' . $buble . ' sink=' .$sink . ' / <br/>';				  
			}
			if ($swaped == "false") {	
				//echo '<pre>break at i='. $i . ' </pre>';		
				break;
			}
		}
		//echo '<pre>loop=' . $this->count . '  </pre>';
		return $sortArray;
	}
	
	private function selectionSort($sortArray){
		for($i=0; $i < count($sortArray); $i++){			
			$k = $i;
			for($j = $i + 1; $j < count($sortArray); $j++){
				$this->count++;
				if($sortArray[$j] < $sortArray[$k]){
					$k = $j;
				}				
			}
			//swapping					
			list($sortArray[$k],$sortArray[$i]) = array($sortArray[$i],$sortArray[$k]);
		}
		
		//echo '<pre>loop=' . $this->count . ' </pre>';		
		return $sortArray;
	}		
	
	private function insertionSort($sortArray){
		for($i=1; $i < count($sortArray); $i++){
			//echo ' i='.$i. '<br/>';
			for($k=$i; $k>0 && $sortArray[$k] < $sortArray[$k - 1]; $k--){
				$this->count++;
				//echo '<pre>/count='.$this->count.' k='. $k.' a[k]='.$sortArray[$k].' a[k-1]='. $sortArray[$k-1] .'/<br/>';
								
				//swapping
				list($sortArray[$k-1],$sortArray[$k]) = array($sortArray[$k],$sortArray[$k-1]);
				
				//print_r($sortArray);
				//echo '</pre>';
			}
			//echo 'i='. $i . '<br/>';
		}
		//echo '<pre>loop=' .$this->count . ' </pre>';
		return $sortArray;
	}
	
	private function shellSort($sortArray){
		$h = 1;
		while($h<count($sortArray)){
			$h = 3*$h + 1;
		}
		
		while ($h > 0){
				
			$h = $h/3;
			for($k=0; $k < $h; $k++){
				
			}
		}
		
		return $sortArray;
	}
	
	private function mergeSort($sortArray){
		//check if the sub-array  is one member. if it is, no need to sort and return it
		if(floor(count($sortArray) / 2) == 0){
			return $sortArray;
		} 		
		
		//define where to split the inputed array
		$m = floor(count($sortArray) / 2);		
		
		// recursively sort 2 sub arrays
		$sub1 = array_slice($sortArray,0,$m);
		$sub2 = array_slice($sortArray,$m,count($sortArray));
		$sub1Sorted = $this->mergeSort($sub1);
		$sub2Sorted = $this->mergeSort($sub2);
		
		// merge 2 sorted-sub arrays tobether again		
		$sortArray = array_merge($sub1Sorted, $sub2Sorted);
		
	/* 	echo '<pre> sub1 ';
		print_r($sub1Sorted);
		echo 'merge array ';
		print_r($sortArray);
		echo '</pre>'; */
		
		//clone the 1st subarray;
		$bArr = $sub1Sorted;
		
		$i = 0; $j = $m; $k = 0;
		
		//compare 2 array: a clone of sub1 and the 2nd part of merged array (which is sub2). 
		//Depend on values, each member of 2 arrays will be placed into the final position		
		while($i <= $m-1 && $j <= count($sortArray)-1){
			
			//echo '/i='.$i.' j='. $j .' k='. $k . ' / <br/>' ;
			
			//main sort
			$this->count++;
			$sortArray[$k++] = ($sortArray[$j] < $bArr[$i]) ? $sortArray[$j++] : $bArr[$i++];	
			
			/* echo '<pre> sub1 ';
			print_r($sub1Sorted);
			echo ' full ';
			print_r($sortArray);
			echo '</pre>'; */				
		}
		
		//echo '$$$$$ second while $$$$$ <br/>';
		
		// if the pointer of the clone of sub1 doesn't pass of sub1's length, means sub1 have greater values, 
		// continue to place it at the end of merged array
		while($i <= $m-1){
			//echo '/i='.$i. ' k='. $k . ' / <br/>' ;
			
			//main sort
			$this->count++;
			$sortArray[$k++] = $bArr[$i++];
			
			/* echo '<pre> sub1 ';
			print_r($sub1Sorted);
			echo ' full ';
			print_r($sortArray);
			echo '</pre>'; */
		}
		
		/* echo '<pre>';
		print_r($sortArray);
		echo '</pre>'; 
 		exit; */
		//echo '<pre>loop=' . $this->count . '</pre>';
		return $sortArray;
	}
	
	private function heapSort($sortArray){
		$n = count($this->arr);
		//heapify
		for($i=(floor($n/2)); $i >= 0; $i--){
			$this->sink($this->arr, $i, $n);
		}
		
		echo '<pre>';
		print_r($this->arr);
		echo '</pre>';
		exit;
		
		
		echo '$$$$$ sort down $$$$$ <br/>';
		
		//sortdown
		for($i=0; $i < $n; $i++){		
							
			//swapping
			//echo '/ [n-i]=' . ($n-$i-1) . '/ <br/>';
			list($this->arr[($n-1) - $i],$this->arr[0]) = array($this->arr[0],$this->arr[($n-1) - $i]);
			
			//sinking
			$this->sink($this->arr, 0, $n-$i);
		}
		
		
		
		
		
		return $this->arr;
	}
	
	//sink from i in  a[1,n]	
	//function sink, just for heapSort
	private function sink($a, $i, $n){
		//{lc,rc,mc} = {left, right, max} child index
		
		echo 'before sink <pre>';
		print_r($a);
		echo '</pre>';
		
		//compute lc
		$lc = $i * 2;
		echo  ' i='. $i . ' lc='. $lc . ' '  ;
		
		if($lc >= $n ){
			echo ' no child <br/>';
			return;
			//no child
		}
		
		//compute rc
		$rc = $lc + 1;
		echo 'rc='. $rc . ' ';
		
		//compute mc
		$mc = ($rc >= $n) ? $lc : ($a[$lc] > $a[$rc]) ? $lc : $rc;
		echo 'mc='. $mc  .' ';
		
		if($a[$i] >= $a[$mc]){
			echo 'heap is ordered <br/>';
			return;
			//heap is order
		}
		
		echo ' --- before swap a[i]='.$a[$i] . ' a[mc]=' . $a[$mc];
		
		//swapping
		list($a[$mc],$a[$i]) = array($a[$i],$a[$mc]);
		
		echo ' after swap a[i]='.$a[$i] . ' a[mc]=' . $a[$mc];
		
		//$this->globalArr = $a;
		
		/* echo '<pre>';
		print_r($a);
		echo '</pre>'; */
		
		//recursive call itself
		echo '<br/>';
		
		$this->arr = $a;
		
		echo 'after sink <pre>';
		print_r($a);
		echo '</pre>'; 
		
		
		$this->sink($a, $mc, $n);
	}
	
	private function quickSort($a){
		//echo '$$$$$$$$$$$$$$$$$$$$$ another quick sort $$$$$$$$$$$$$$$$$$$$$$$$$$ <br/>';
		
		//have 1 element, no need to sort
		if(count($a) ==1 || count($a) ==0){
			return $a;
		}
		
		/* echo '<pre>';
		print_r($a);
		echo '</pre>'; */
		
		//check if this array is sorted
		/* $tempArray = $this->mergeSort($a);
		if(json_encode($a) == json_encode($tempArray)){
			echo 'array is sorted <br/>';
			return $a;
		} */
		
		//choose pivot
		$randomNumber = rand(0, count($a)-1);
		//swapping
		list($a[$randomNumber],$a[0]) = array($a[0],$a[$randomNumber]);
		
		//2-way partition
		$k = 0;
		for($i=1; $i < count($a); $i++){
			$this->count++;
			if($a[$i] < $a[0] ){
			//swap a[++k,i]
			$tempK = ++$k;
			list($a[$i],$a[$tempK]) = array($a[$tempK],$a[$i]);
			//echo '/i='.$i.'k='.$k.' count='. count($a) . '/<br/>';
			}
			/* echo '<pre>';
			print_r($a);
			echo '</pre>'; */
		}
		//swap a[1,k]
		list($a[$k],$a[0]) = array($a[0],$a[$k]);
				
		//echo 'k='.$k.' count='. count($a) . '/<br/>';
		# recursive sorts
		$sub1 = array_slice($a,0,$k);
		$sub2 = array_slice($a,$k,count($a));
		$sortedSub1 = $this->quickSort($sub1);
		$sortedSub2 = $this->quickSort($sub2);
		
		$a = array_merge($sortedSub1, $sortedSub2);
		
		return $a;
	}
}